package com.leetcode.partition3;

import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/10/19 9:07
 */
public class LC211添加与搜索单词 {

    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        wordDictionary.addWord("pad");
        System.out.println(wordDictionary.search("b.."));
    }

    private static class WordDictionary {
        private TrieNode root;

        public WordDictionary() {
            root = new TrieNode(' ');
        }

        public void addWord(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (cur.trieNodeMap.containsKey(word.charAt(i))) {
                    //如果存在当前的字典树序列串，将当前最后一个字符节点的标识改为true
                    if (i == word.length() - 1) cur.trieNodeMap.get(word.charAt(i)).end = true;
                    cur = cur.trieNodeMap.get(word.charAt(i));
                    continue;
                }
                //当前字典树不存在当前字符，创建字符并添加到字典树中
                TrieNode trieNode = new TrieNode(word.charAt(i));
                //当前字符是单词的最后一个，理当改为true
                if (i == word.length() - 1) trieNode.end = true;
                cur.trieNodeMap.put(word.charAt(i), trieNode);
                cur = cur.trieNodeMap.get(word.charAt(i));
            }
        }

        public boolean search(String word) {
            TrieNode cur = root;
            return search(word, 0, cur);
        }

        private boolean search(String word, int startIndex, TrieNode cur) {
            for (int i = startIndex; i < word.length(); i++) {
                if (word.charAt(i) == '.') {
                    boolean res = false;
                    //找出当前字典树节点下的所有孩子节点，并递归进行遍历
                    for (Map.Entry<Character, TrieNode> entry : cur.trieNodeMap.entrySet()) {
                        res = search(word, i + 1, cur.trieNodeMap.get(entry.getKey()));
                        //如果找到了有匹配的子串，就没有必要继续迭代递归了
                        if (res) break;
                    }
                    //返回当前.的查找结果
                    return res;
                }
                //正常字典树的匹配操作
                if (cur.trieNodeMap.containsKey(word.charAt(i))) {
                    cur = cur.trieNodeMap.get(word.charAt(i));
                } else {
                    return false;
                }
            }
            return cur.end;
        }
    }

    private static class TrieNode {
        char data;
        Map<Character, TrieNode> trieNodeMap;
        boolean end;

        public TrieNode(char data) {
            this.data = data;
            trieNodeMap = new HashMap<>();
            end = false;
        }
    }
}
